% !Mode:: "TeX:UTF-8"

\chapter{基于DSP微处理器应用的最优调度和集群间通信}

\section{引言}
数字信号处理和多媒体应用程序需要大量计算，同时具有实时性需求。在这样应用程序中的计算引擎不同于通用的，它更
趋向于嵌入式系统。因为这些程序在一般系统中有大量指令级并行，平均数字信号处理指令集并行为21，多媒体指令集并
行大约为18，为了满足严格的性能要求，高端DSP处理器实验功能单元幅值来最大化指令集并行。然而，集中的注册文件呈
现出高的区域复杂性，访问延迟和能耗。区域复杂度是由N个功能单元直接读写造成的，复杂度为N3；访问延迟为N3/2；能
耗为N3，其中N是共享的集群数。因此，系统级文件被分层多个子块来减少大面积开销和访问竞争。每个寄存器文件子块联
合相关的功能单元组成一个集群。对于多集群架构，集群数目可以由硬件实现来决定。每个集群可以以较小的开销从其相关
寄存器文件子块中读写，集群之间访问开销比较大。

在多集群架构中集群间连接网络是一个瓶颈，影响整个性能。一些类似于展开和重定时技术可以开发和增加程序并行。但是
，这会造成集群间数据传输增多，为了达到性能要求，这就给集群间通信网络施加了更大压力。集群间通信网络可以是一个
基于总显得网络或者是一个点到点的网络。隐含的假设是任意两个集群之间存在一条通路，以至于集群间可以进行数据传
输。点到点的网络是充分连接的，相连的集群中有一对单项的连接存在于每个功能单元和寄存器文件之间。尽管拓扑图提
供了最大的传输可行性，其高硬件开销以及潜在的第连接实用性和低可扩展性为实际使用带来了障碍。因此，部分连接的
点到点网络，如：仅在两个相邻集群之间有物理连接是比较实际和流行的。然而对于不是物理连接集群之间数据传输，他
们必须通过具有物理连接的中间集群桥接，造成至少一个计算停止。另一方面，相比点到点连接，基于总线连接更具适应性
，如一个全局总线连接所有集群，这样可以在所有相连的集群间传递数据。但是，在多个集群间同时进行数据交换时，单一
全局总线可能会成为性能的瓶颈。另外，带有多个总线段的冗长的总线具有高能耗，区域开销，时钟歪斜和传播延迟。因
此需要有更少和更短的总线。论文研究如何获取高性能和连接弹性与点到点全连接相似的情况下能维持使用总线的效益。
为了获取这个目标，论文将研究如何以智能方式调度集群之间数据传输。
为了减少集群的DSP处理器上的调度开销，DSP应用程序通常将显式的调度信息嵌入到代码中来实现静态编译。例如：使用
VLIW代码，每个指令包含4,8，或更多操作，可以显示的指定功能单元和关联的寄存器。高级合成上的调度室一个很重要的
任务，能决定哪个操作在哪个硬件资源上的那个时间段执行。传统调度技术一般将目标放在操作和通过流水线开发并行来
最小化调度时长或最小化资源。这些调度算法在对单个处理机构时效果很好，因为他们不需要考虑集群间通信开销。对于
多集群或多喝架构，集群间通信开销是不能被忽视的。因此，各种各样的调度算法已经将集群间通信开销列入考虑，如论
文\cite{cnproceed}[2]、[8]、[24]和[30]提出的方法。主要有两类集群间通信有意识调度算法。一类是论文\cite{cnarticle} 中基于列表调度被称为根
据时间估计最高级优先。对于这类中的调度算法，根据节点基本顺序调度。节点基本是沿着通路从一个节点到一个出口节
点计算最大开销和。最高级节点总是比其他节点优先调度。另外一类是聚类。图形输入节点被分组成簇。聚类算法中有两
类基本的。一类是基于关键路径。如果主序列中任务属于部分集群图中最长路径将被分组。另外一种是基于结构属性和优
先级任务图分解的。近来，研究扩展到了异构多核架构。不管集群间通信有意识调度算法属于哪一类，它的研究目标是最
小化集群间通信和整体指向时间。图中每个任务集群间通信网络和通信开销作为输入已经给定。集群间通信网络对总线需
求数量总是由并发数据传输的峰值决定。对于数据传输，两个常用的传输策略是尽快和尽可能晚。对于ASAP，一旦可用，
数据传输马上给接收集群。相反，对于ALAP，数据先存储在发送集群的寄存器文件中知道接收集群需要的时候。论文将研
究新的高指令集并行调度技术来减少集群间数据传输需求和研究新的集群数据传输策略来最小化集群间网络总线需求，同
时保证程序嵌入式指令级并行而不影响调度时长(完成时间)。
工作中采用了一个应用程序的带部分连接总线的特定方法来设计无死锁集群间连接网络。论文第一部分，调度程序作为输入，集群间连接网络以最小硬件开销来设计去满足性能需求。通过获取DSP应用程序的调度信息，我们能决定集群间连接网络的最小总线需求。这个最小总线巨大算法将任意给定的调度作为输入，以多项式时间计算最小总线数。其还可以为相关集群间数据传输产生最有无死锁调度。随后，论文就总线段而言，提出了一个算法，在集群间连接网络拓扑图下通过部分连接总线来最小化整体总线长度。总线段是两个相邻集群之间的物理连接。不同的调度对于同一个DSP应用程序可能在有不同数目的最小总线需求，论文进一步提出一个调度算法来最小化集群间数据传输，来减少集群间连接总线需求数目。

总之，本文贡献如下：
\begin{itemize}
  \item 提出了最小总线算法；该算法在给定多项式时间内决定集群间数据传输所需的最少总线数。
  \item 在上一步提到的最少总线数前提下，确定潜在的集群间连接网络拓扑。连接网络使用部分连接总线
取代全局总线来减少整体总线段，保证同级数据传输可行性和全局总线给特定应用程序。
  \item 提出了一个计算和通信协调调度算法，产生最少总线算法的调度输入来减少所需总线的最少数量。
\end{itemize}

文章剩下部分组织如下：第二节介绍目标处理架构和DSP应用程序模型。第三节简要介绍提出的算法。第四节详细介绍算法。第四节A部分介绍最少总线算法以及证明了它是多项式时间可解。第四节B部分 算法获取集群间连接网络拓扑。第五节介绍调度算法，该算法产生MinBus算法的输入，可以减少最少需求总线数目。第六节给出了实验结果。第七节总结与讨论，讨论如何扩展论文中特定程序到多个应用程序和如何工作在多核异构处理架构上。

\section{基本原理}
\subsection{DSP处理器集群建模}

图1表示一个一般的集群DSP处理器模型，它包含了N个集群。每个集群包含多个功能单元和一个寄存器文件。集群中的功能
单元可以在控制的任何步骤以低开销直接访问其寄存器文件。然而，当一个功能单元需要访问一个远程寄存器文件时，内
容通过通信功能单元传输到集群间连接网络。论文中，我们考虑集群间连接网络由一系列部分连接总线组成。部分连接总
线仅仅连接到那些有需要依赖于它进行集群间数据传输需求和功能类似于点到点连接来在集群对之间传输数据的集群。
在集群连接间支持多播。

当数据在计算或者临时存储在原始集群的寄存器文件时，集群间数据可以在同一控制步骤使用直到调度转移时间。目的
寄存器文件中额外的时间可能在目的功能单元访问的之前用到。实验在第二节DSP基准上完成，将证明用于存储临时集群
间通信数据的寄存器数量不超过10.论文中，假设在源集群和目标集群中用来存储临时数据的寄存器文件足够。
\subsection{动机}
这节我们使用图2中给的DAG例子来简单讨论提出方法来导出集群间连接网络最少部分连接总线。下层架构和图1所示相同。
布置了三个集群，每个集群包含了一个加法器，一个乘法器和一个寄存器文件。
使
用HLFET算法对图2中案例调度结果显示在图3(a)。根据节点优先级对其进行调度，优先级由相关节点数决定的。被调度节
点被分配到第一个可用的集群，如图3(a)所示。一次循环包含了五个控制步骤。图3(a)中显示了集群间数据传输需求，用
带箭头的线从发生方指向接收方。为了清除确定各控制步骤集群间数据传输，图3(b)给出了数据传输图。每个控制步骤下
的线段表示可能的数据传输。在段左边标记的操作节点为发送方，在段右边标记的节点为接收方。变量xij表示控制步骤j
可能有第i个数据传输。例如，变量x31和x32分别表示集群2上节点D到集群1上节点F在控制步骤1和2数据传输。数据传输需
要一个控制步骤，x31和x32都可以发生。

图4(a)展示的为数据传输情景。在该情景中，"not going to happen"数据传输被用虚线段标记，如：有的标记为x32。一次迭代中最大并发数据传输定义为集群间连接网络在没有扩展调
度时长下最小PC总线需求，图4(a)中最少需要3个PC总线。可能的集群间连接策略如图4(b)所示。一个总线连接集群1和集群
2，分布在控制步骤1,2,3来传输数据x11，x42和x63。另外一个总线连接所有的三个集群，用来分布在控制步骤1,2传输数据
x31和x52。第三个总线连接集群2和集群3来在控制步骤1传输数据x21。更少的PC总线会延长调度时长。

如果数据传输如图5(a)那样被调度，那么一次迭代中任意控制步骤最大的并发数据传输数据为2.在该数据传输场景，数据由
节点D传到节点F将发生在控制步骤2中而不是之前的场景中的控制步骤1。节点E到H和节点G到I中数据传输也是一样的。因此
两个PC总线对于集群间连接网络在没延长调度时长条件下是足够的。相应的集群间连接策略如图5(b)所示。

图6(a)针对图2中的DAG给出了一个新的计算策略。相比图4(a)的调度，传输的数据从原来的6减少到了3，如图6(b)所示。结
果，一条总线将足够满足所有的数据传输要求，而不影响调度时长。相应的集群间连接策略如图6(c)所示。

从例子中可以看出，集群间数据传输策略和计算策略很大程度影响最小PC总线需求数量。本节中案列足够就简单以至于很容
易分析。对于复杂情况，在第四节中，我们将引入系统方法，在最有集群间数据传输调度下决定最小总线需求数和导出连接
网络拓扑图来最小化整体总线段。第五节将介绍调度算法，它可以产生调度来减少最小PC总线需求数。
\section{设计具有最小总线需求的集群间连接网络}
本节介绍我们的方法设计集群间连接网络。方法被分为两个步骤：第一，在保证性能不降低的条件下决定最少需求总线。
我们证明了可以在多项式时间内解决该问题。第二，用第一步中的基于数据传输调度的部分连接总线导出集群间连接网络
拓扑图。导出的拓扑图将展示集群如何被连接到部分连接的总线上来减少整体总线段。
\subsection{觉得集群间连接网络的最小总线需求数}
我们方法使用第二节给出的架构和应用程序模型。遵循上一节中的限制条件。
\begin{description}
  \item[1)] 时间限制。给定一个静态调度DSP应用程序，只要操作是在产生之后消耗之前，集群间数据传输就是灵活的。
      \item[2)] 总线数限制。在任意给定时间，同时传输的数据不能超过可用的总线数。
\end{description}
构造数据传输变量算法(CDTV)从预先排好的DSP应用程序中获取时间限制，创建数据传输图。CDTV算法详细过程在算法1中
给出。输入是如图3所示的时间表。CDTV产生一列传输变量，标注为xij，表示第i个数据传输可以发生在第j个控制步骤。
Xij可以由以下值：

 运行CDTV算法，一系列xij如图3(b)所示，相应的时间表在图3(a)中产生。
如算法2所示，对于给定的时间表，为了保证其嵌入式指令级并行而不增加调度时长(一次迭代完成时间)，MinBus算法能决定集群间连接总线数量需求的最小值。最小集群间连接总线需求数上届为M，M是一次迭代中集群间数据传输数目总和。下限为0，当没有集群间数据传输时，总线需求为0。通过二分搜索，MinBus通过调用算法3中展示的数据传输策略功能寻找是否存在一个有效的集群间数据传输调度小于b个总线限制，最终找到最小总线数b。因此，一个有效的集群间数据传输调度产生了，它可以指定什么样的数据可以在哪个控制步骤中传输来获取最小的总线需求数。
算法数据传输策略首先调用算法CDTV为给定的调度产生数据传输变量集合。约束等式(1)主要重申一个集群间数据传输需要一个控制步骤。约束等式(2)陈述了在任意迭代的单个控制步骤中最大并发集群间数据传输应该小于总线约束b。b代表最小的集群间连接网络所需的总线数。目标是在b个总线约束下决定XT中每个xij的值。
对于图2中的DAG例子，在创建一系列数据传输变量xij后，添加总线约束，形成如下等式。等式EQ1-EQ6表示每个数据传输需要一个控制步骤。等式EQ7-EQ10表示最多b个同时传输数据。
等式(1)-(10) 可以重新写成如下矩阵格式：
其中s1,s2,s3,s4选的是大于0的整数。定义如下：
因此(1)可以简化为CY=V。
满足(1),我们获取到最小的b是2，XT=(1,1,0,1,1,0,1,1)，XT定义为(x11,x21,x31,x42,x52,x53,x63,x64)。

